﻿
#include <string>
#include <iostream>
#include <thread>
#include <vector>
#include <map>
#include <stack>
#include <algorithm>
#include <queue>
#include <tuple>
#include <bitset>

constexpr int16_t N = 4; //节点数目
constexpr int32_t MAX = 9999;

/*
	临界表节点
	保存下一个点和到下一个点边权重
*/
class node {
public:
	int32_t p; //点
	int32_t w; //边长
	node(std::initializer_list<int32_t> list) {
		auto it = list.begin();
		p = *(it++);
		w = *it;
	}
};




class Solution {
public:

	std::vector<node>  g[N]; //临界表
	std::vector<int32_t> path; //保存路径

	std::bitset<N> vis; //标记哪个点被访问过了
	int32_t minLength = MAX;

	int32_t minUp;//最小上界
	int32_t maxLow;//最大下界

	Solution() {
		minLength = MAX;
		maxLow = -MAX;
	}
	
    /*
		输入参数：bPoint起点 
		输出参数：outRes输出路径;
				 outLen输出长度
	*/
	void calculate(int32_t bPoint, std::vector<int32_t> &outRes, int32_t &outLen) {

		vis[bPoint] = true;
		path.emplace_back(bPoint);

		dfs(bPoint, 0, 0, outRes);

		outRes.emplace_back(bPoint);
		outLen = minLength;

	}

	/*
		贪心算法算部分解的上界
	*/
	int greedy() {
		//路径长度
		int32_t res = 0;

		//深复制
		std::bitset<N> temp_vis = vis;
		
		//取路径中当前走到的点,一开始从这个点出发扫描
		int32_t j = path.back();
		int8_t count = 0;

		
		while (true) {

			auto link = [&]()->std::tuple<bool, int32_t> {
				for (auto temp : g[j]) {
					if (temp.p == 0) return std::make_tuple(true, temp.w);
				}
				return std::make_tuple(false, -1);
			};

			//迭代结束标志,跳出while循环
			if (auto[status, len2b] = link(); count == N - 1 && status) {
				res += len2b;
				break; 
			}
			int32_t minP;//最小点
			int32_t minW = MAX;//最小边
			for (auto k : g[j]) {

				if (minW <= k.w && (!temp_vis[k.p])) {
					minW = k.w;
					minP = k.p;
				}
			}
			temp_vis[minP] = true;
			j = minP;

			res += minW;
			count++;//点数加一
		}
		return res;
	}

	/*
		算部分解下界
		这里的参数接收length
	*/
	double low(int32_t length) {
		//r1行不在路径上的最小元素，即r1点发出的不在路径上的最小边
		int32_t minLen1 = MAX;
		for (auto t : g[path.front()]) {
			if (minLen1 > t.w && (!vis[t.p]) ) {
				minLen1 = t.w;
			}
		}


		//rk行不在路径上的最小元素，即rk点发出的不在路径上的最小边		
		int32_t minLen2 = MAX;
		for (auto t : g[path.back()]) {
			if (minLen2 > t.w && (!vis[t.p])) {
				minLen2 = t.w;
			}
		}
		
		//不在路径上的rj行最小的两个元素
		//i为rj
		int32_t rj_sum = 0;
		for (auto i = 0; i < N && (!vis[i]); i++) {
			int32_t firstMin = MAX;
			int32_t secMin = MAX;
			for (auto j : g[i]) {
				if (j.w < firstMin) {
					secMin = firstMin;
					firstMin = j.w;
				}
				else if (j.w > firstMin && j.w < secMin) {
					secMin = j.w;
				}
			}
			rj_sum += firstMin + secMin;
			
		}

		return static_cast<double>(2 * length + minLen1 + minLen2 + rj_sum);

	}



	void dfs(int32_t i, int32_t count, int32_t length, std::vector<int32_t> &outRes) {


		/*
			计算上下界
		*/
		int32_t curUp = greedy();
		double curLow = low(length);
		
		if (curLow == curUp) {
			//如果节点v的UB(v) = LB(v)，则该节点不用继续搜索， 直接用LB(v) 作为其可到达的最优值，对cBest进行更新

		}
		else if(curLow > curUp) {
			//剪枝
			return;
		}
		else if (curUp <= length) {
			//剪枝
			return;
		}
		else {
			//更新上下界
			if (curUp <= minUp) {
				minUp = curUp;
			}
			if (curLow >= maxLow) {
				maxLow = curLow;
			}
			
		}

		

		/*
			判断当前点i是否和起点连接
			若连接则返回stauts=true和到起点权值
			否则则返回status=false和-1
		*/
		auto link = [&]()->std::tuple<bool, int32_t> {
			for (auto temp : g[i]) {
				if (temp.p == 0) return std::make_tuple(true, temp.w);
			}
			return std::make_tuple(false, -1);
		};



		/*
			递归终止条件
			扫描完所有点，更新最小路径
		*/
		if (auto[status, len2b] = link(); count == N - 1 && status) {

			minLength = [&](int32_t x, int32_t y)->int32_t {return x < y ? x : y; }(minLength + len2b, length + len2b);
			outRes.clear();
			std::copy(path.begin(), path.end(), std::back_inserter(outRes));
		}

		for (auto j : g[i]) {

			//剪枝
			if ((!vis[j.p]) && length + j.w < minLength) {

				[&]() {vis[j.p] = true; path.emplace_back(j.p); }();

				dfs(j.p, count + 1, length + j.w, outRes);

				[&]() {vis[j.p] = false; path.pop_back(); }();
			}

		}

	}

};

int main(int argc, char* argv[]) {

	Solution s;
	/*
	s.g[0].push_back(node{ 1, 10 });
	s.g[0].push_back(node{ 2, 6 });
	s.g[0].push_back(node{ 3, 4 });

	s.g[1].push_back(node{ 0, 10 });
	s.g[1].push_back(node{ 2, 5 });
	s.g[1].push_back(node{ 3, 10 });

	s.g[2].push_back(node{ 0, 6 });
	s.g[2].push_back(node{ 1, 5 });
	s.g[2].push_back(node{ 3, 20 });

	s.g[3].push_back(node{ 0, 4 });
	s.g[3].push_back(node{ 1, 10 });
	s.g[3].push_back(node{ 2, 20 });
	*/
	/*s.g[0].push_back(node{ 1, 3 });
	s.g[0].push_back(node{ 2, 1 });
	s.g[0].push_back(node{ 3, 5 });
	s.g[0].push_back(node{ 4, 8 });

	s.g[1].push_back(node{ 0, 3 });
	s.g[1].push_back(node{ 2, 6 });
	s.g[1].push_back(node{ 3, 7 });
	s.g[1].push_back(node{ 4, 9 });

	s.g[2].push_back(node{ 0, 1 });
	s.g[2].push_back(node{ 1, 6 });
	s.g[2].push_back(node{ 3, 4 });
	s.g[2].push_back(node{ 4, 2 });

	s.g[3].push_back(node{ 0, 5 });
	s.g[3].push_back(node{ 1, 7 });
	s.g[3].push_back(node{ 2, 4 });
	s.g[3].push_back(node{ 4, 3 });


	s.g[4].push_back(node{ 0, 8 });
	s.g[4].push_back(node{ 1, 9 });
	s.g[4].push_back(node{ 2, 2 });
	s.g[4].push_back(node{ 3, 3 });
	*/
	s.g[0].push_back(node{ 1, 9 });
	s.g[0].push_back(node{ 2, 19 });
	s.g[0].push_back(node{ 3, 13 });

	s.g[1].push_back(node{ 0, 21 });
	s.g[1].push_back(node{ 3, 14 });

	s.g[2].push_back(node{ 3, 17 });
	s.g[2].push_back(node{ 0, 1 });


	s.g[3].push_back(node{ 0, 13 });
	s.g[3].push_back(node{ 1, 80 });
	s.g[3].push_back(node{ 2, 10 });


	int min = 9999;
	for (int i = 0; i < N; i++) {
		std::vector<int32_t> res;
		int32_t len;
		s.calculate(2, res, len);
		min = len < min ? len : min;
	}

	/*
	for (auto i : res) {
		std::cout << i << std::endl;
	}
	*/
	std::cout << min << std::endl;
	return 0;
}